package util;

import java.util.Vector;

import structures.*;

public class Iso {
	
	public static boolean isIso(StaticGraph g1, StaticGraph g2) {
		Vector<String> nodes = g1.getNodes();
		Vector<Vector<String>> permute = permute(nodes);
		boolean equals = false;
		for(int i = 0; i < permute.size(); i++) {
			equals = equals || equals(buildAdjMatrix(g2, g2.getNodes()), buildAdjMatrix(g1, permute.get(i)));
		}
		return equals;
	}

	
	
	private static double[][] buildAdjMatrix(StaticGraph g, Vector<String> list) {
		double[][] adjMatrix = new double[list.size()][list.size()];
		for(int i = 0; i < list.size(); i++) {
			for(int j = 0; j < list.size(); j++) {
				adjMatrix[i][j] = g.getEdge(list.get(i), list.get(j));
			}
		}
		return adjMatrix;
	}
	/**
	 * Checks to see if the two arrays are equal.
	 * @param a
	 * @param b
	 * @return
	 */
	
	private static boolean equals(double[][] a, double[][] b) {
		if(a.length != b.length || a[0].length != b[0].length) {
			return false;
		}
		for(int i = 0; i < a.length; i++) {
			for(int j = 0; j < a[0].length; j++) {
				if(a[i][j] != b[i][j]) {
					return false;
				}
			}
		}
		return true;
	}

	
	/**
	 * Recursively finds all permutations of the given list.
	 * Works.
	 * @param list
	 * @return
	 */
	
	private static Vector<Vector<String>> permute(Vector<String> list ) {
		Vector<Vector<String>> results = new Vector<Vector<String>>();
		if(list.size() == 1) {			
			results.add(list);
			return results;
		}
		else {
			for(int i = 0; i < list.size(); i++) {
				Vector<String> temp = new Vector<String>();
				temp.addAll(list);
				String s = temp.remove(i);
				Vector<Vector<String>> permutation = permute(temp);
				for(int j = 0; j < permutation.size(); j++) {
					permutation.get(j).add(0, s);
					results.add(permutation.get(j));
				}
			}
			return results;
		}
	}
	
	
}
